#include <cmath>
#include <math.h>
#include <algorithm>
#include <limits>
#include "segment.h"
#include <queue>

bool plain_intersection(double x1, double x2, double x3, double x4)
{
	return !(std::max(x1, x2) < std::min(x3, x4)
			|| std::max(x3, x4) < std::min(x1, x2));
}

bool bound_boxes_intersects(double x1, double y1, double x2, double y2,
		double x3, double y3, double x4, double y4)
{
	return plain_intersection(x1, x2, x3, x4)
			&& plain_intersection(y1, y2, y3, y4);
}

std::pair<double, double> split(double a, size_t s)
{
	double c = ((1LL << s) + 1LL) * a;
	double ab = c - a;
	double hi = c - ab;
	double lo = a - hi;
	return std::pair<double, double>(hi, lo);
}

std::pair<double, double> multiply(double a, double b)
{
	double res = a * b;
	size_t s = std::numeric_limits<double>::digits / 2
			+ std::numeric_limits<double>::digits % 2;
	double a_hi, a_lo, b_hi, b_lo;
	std::pair<double, double> pair = split(a, s);
	a_hi = pair.first;
	a_lo = pair.second;
	pair = split(b, s);
	b_hi = pair.first;
	b_lo = pair.second;
	double e1 = res - (a_hi * b_hi);
	double e2 = e1 - (a_lo * b_hi);
	double e3 = e2 - (b_lo * a_hi);
	return std::pair<double, double>(res, a_lo * b_lo - e3);
}

int exponent(double d)
{
	union
	{
		double double_;
		long long long_long_;
	} dd;
	dd.double_ = d < 0 ? -d : d;
	int res = dd.long_long_ >> 52;
	res = res - 1023;
	return res;
}

double pow2(int exponent)
{
	union
	{
		double double_;
		long long long_long_;
	} dd;
	dd.long_long_ = ((long long) exponent + 1023) << 52;
	return dd.double_;
}

int left_turn_more_accurate(segment const &s, point const &p)
{
	double eps = 4 * std::numeric_limits<double>::epsilon();
	point a = s.a_, b = s.b_, c = p;
	double doubles[12];
	std::pair<double, double> pair = multiply(b.x_, c.y_);
	doubles[0] = pair.first;
	doubles[1] = pair.second;
	pair = multiply(-b.x_, a.y_);
	doubles[2] = pair.first;
	doubles[3] = pair.second;
	pair = multiply(-a.x_, c.y_);
	doubles[4] = pair.first;
	doubles[5] = pair.second;
	pair = multiply(-b.y_, c.x_);
	doubles[6] = pair.first;
	doubles[7] = pair.second;
	pair = multiply(b.y_, a.x_);
	doubles[8] = pair.first;
	doubles[9] = pair.second;
	pair = multiply(a.y_, c.x_);
	doubles[10] = pair.first;
	doubles[11] = pair.second;
	std::priority_queue<double> positive, negative;

	for (size_t i = 0; i < 12; i++)
	{
		double val = doubles[i];
		if (val > 0)
			positive.push(val);
		if (val < 0)
			negative.push(-val);
	}
	while (true)
	{
		size_t positive_size = positive.size();
		size_t negative_size = negative.size();
		if (negative_size == 0 && positive_size == 0)
			return 0;
		if (positive_size == 0)
			return -1;
		if (negative_size == 0)
			return 1;
		double a1 = positive.top();
		double b1 = negative.top();
		positive.pop();
		negative.pop();
		if (a1 == b1)
			continue;
		if (a1 > 2 * negative_size * b1)
			return 1;
		if (b1 > 2 * positive_size * a1)
			return -1;
		int e1 = exponent(a1);
		int f1 = exponent(b1);
		if (e1 == f1)
		{
			if (a1 > b1)
				positive.push(a1 - b1);
			else
				negative.push(b1 - a1);
		}
		else if (e1 < f1)
		{
			double u = pow2(e1 + 1);
			negative.push(b1 - u);
			negative.push(u - a1);
		}
		else
		{
			double u = pow2(f1 + 1);
			positive.push(a1 - u);
			positive.push(u - b1);
		}
	}
	return 0;
}

int left_turn(segment const & s, point const & p)
{
	double eps = 4 * std::numeric_limits<double>::epsilon();
	eps *= std::abs((s.b_.x_ - s.a_.x_) * (p.y_ - s.a_.y_))
			+ std::abs((s.b_.y_ - s.a_.y_) * (p.x_ - s.a_.x_));

	double res = (s.b_.x_ - s.a_.x_) * (p.y_ - s.a_.y_)
			- (s.b_.y_ - s.a_.y_) * (p.x_ - s.a_.x_);
	if (std::abs(res) > eps)
	{
		if (res > 0)
			return 1;
		if (res < 0)
			return -1;
	}
	return left_turn_more_accurate(s, p);
}

bool has_intersection(double x1, double y1, double x2, double y2, double x3,
		double y3, double x4, double y4)
{
	if (!bound_boxes_intersects(x1, y1, x2, y2, x3, y3, x4, y4))
		return false;
	point point1(x1, y1), point2(x2, y2), point3(x3, y3), point4(x4, y4);
	if (left_turn(segment(point1, point2), point3)
			* left_turn(segment(point1, point2), point4) > 0
			|| left_turn(segment(point3, point4), point1)
					* left_turn(segment(point3, point4), point2) > 0)
		return false;
	return true;
}

